// Copyright 2024 Tvux
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package _121

// maxProfit
// 核心思想就是买股票的时间肯定在卖股票之前，所以找到一个最低点，就只需要一直往后遍历判断利润是否大于当前最大利润。
func maxProfit(prices []int) int {
	low := prices[0] // 记录当前最大利润区间的左边界
	res := 0         // 返回的最大利润
	for i := 1; i < len(prices); i++ {
		if prices[i]-low > res {
			res = prices[i] - low
		}
		if prices[i] < low {
			low = prices[i]
		}
	}
	return res
}

// maxProfit
// 单调栈
// 核心思想就是用一个单调栈来记录最大利润区间，这个单调栈在这道题是升序的。
// 7, 1, 5, 3, 6, 4
// 单调栈的变化过程：
// 7 - res = 0
// 1 - res = 0
// 1, 5 - res = 4
// 1, 3 - res = 2
// 1, 3, 6 - res = 5 √
// 1, 3, 4 - res = 3
//func maxProfit(prices []int) int {
//	stack := []int{prices[0]} // 初始化单调栈，只有第一个元素
//	res := 0
//	for i := 1; i < len(prices); i++ {
//		if prices[i] > stack[len(stack)-1] {
//			// 如果当前元素比单调栈中最大的元素还要大就加入栈中
//			stack = append(stack, prices[i])
//		} else {
//			// prices[i] <= stack[len(stack)-1]
//			j := len(stack) - 1
//			for ; j >= 0; j-- {
//				if stack[j] < prices[i] {
//					break
//				}
//			}
//			stack = stack[:j+1]
//			stack = append(stack, prices[i])
//		}
//		res = max(res, stack[len(stack)-1]-stack[0])
//	}
//	return res
//}

// maxProfit
// 时间复杂度：O(n^2)，会超时
//func maxProfit(prices []int) int {
//	res := 0
//	for i := 0; i < len(prices)-1; i++ {
//		for j := i + 1; j < len(prices); j++ {
//			if prices[j]-prices[i] > res {
//				res = prices[j] - prices[i]
//			}
//		}
//	}
//	return res
//}
